Computers offer increasingly sophisticated methods of modeling surfaces. Applications of these surface models range from producing realistic display images to providing simulations with accurate surface information.
Referring to FIG. 1, a free-form surface 10 appears in three-dimensional space (e.g., displayed on a computer monitor). Referring to FIG. 2, a surface 10 in a computer modeling program can be thought of as being covered by a connected set of surface patches 12, 14 such as bicubic surface spline patches. One common type of bicubic surface spline is a Bezier-Spline (B-Spline). Referring to FIG. 3, control vertices 16 offer computer surface modelers an intuitive method of controlling the contour of a selected patch 12. Moving a control vertex 16 causes a corresponding change in the contour of patch 12. For example, moving control vertex 16a could significantly alter the coordinates"" of the upper right portion of patch 12. To a lesser extent, the movement of control vertex 16a may also effect the lower left portion of patch 12.
Referring again to FIG. 2, each patch of the surface 10 has a corresponding set of control vertices. Adjoining patches (e.g., patch 12 and patch 14) share control vertices. Thus, moving a single control vertex affects several neighboring surface patches. However, this movement has no effect on patches not sharing the moved control vertex. Thus, control vertices 16 provide a convenient tool for adjusting contours of a local area of neighboring patches.
Referring to FIG. 4, although a graphical user interface (GUI) that allows a user to visually move control vertices (e.g., by selecting and dragging a control vertex) may shield a modeler from the mathematics involved, the coordinates of the control vertices 16 act as the coefficients of a set of functions 22 that can determine the contour of a B-Spline patch 12 in three-dimensions. Sixteen B-Spline basis functions 22, labeled b1-b16 in FIG. 4, translate a set of parameters u and v 20 that describe a surface location (e.g., the u and v values that describe coordinates of surface location 20 within two-dimensional plane 18) into the coordinates of the location in three-dimensions 24. The process shown in FIG. 4 is known as parameterization. A wide variety of techniques exist for working with parameterized surfaces.
Referring to FIG. 5, subdividing control vertices (i.e., determining a new set of control vertices based on a previous set of control vertices) enables a modeler to gain greater control of over a finer set of patches. Subdivision rules guide determination of new control vertices from existing control vertices. Many different subdivision rules exist. For example, Catmull-Clark subdivision rules produce new control vertices 28 from a set of original control vertices 16 that control a B-Spline patch 12. Catmull-Clark surfaces have many properties which make them attractive as a free-form surface design tool. For example, regardless of the initial topology of a set of control vertices, after a single application of Catmull-Clark subdivision rules, the faces formed by the new control vertices form quadrilaterals. Further, a wide variety of algorithms have been written for these surfaces, for example, fairing algorithms that reduce unwanted surface undulation.
To understand subdivision rules, it is helpful to imagine each control vertex 16 as a corner of a polygon. Catmull-Clark subdivision rules insert new control vertices 28 in the middle of each polygon face formed by the original control vertices 16 and in the middle of each polygon edge other than the outermost edge of the set of polygons. The new set of control vertices 28 also includes original control vertices 16 other than the outermost original control vertices 16. Application of subdivision rules to original control vertices 16 does not, without movement of a new control vertex 28, alter the contour of patch 12. Subsets of the new control vertices 28, however, offer control over sub-patches, essentially making four smaller new patches out of the original surface patch 12. For example, new control vertices 28a-28p control sub-patch 26 of original patch 12. However, B-Spline basis functions (and the basis functions for other surface geometries) can only evaluate a surface when the arrangement of control vertices conform to a rigid set of constraints.
Referring to FIG. 6A, a set of control vertices 30, also known as a xe2x80x9cmeshxe2x80x9d, defines a smooth surface. Each control vertex 30 has a valence corresponding to the number of edges that meet at the vertex. For example, control vertex 32a which appears at the meeting point of three edges has a valence of three. In the case of a free-form surface divided into quadrilateral patches, a vertex having a valence not equal to four is called an extraordinary vertex. FIG. 6A includes three extraordinary vertices. Vertices 32a and 32c have a valence of three. Vertex 32b has a valence of five.
A surface patch controlled by a regular set of control vertices (i.e., a set of control vertices having no extraordinary control vertices) can be evaluated using the basis functions shown in FIG. 4. FIGS. 6A-6C shade regular faces formed by sets of regular control vertices. Referring to FIG. 6B, application of Catmull-Clark subdivision rules to the control vertices 30 of FIG. 6A produces a new set of the control vertices 30xe2x80x2. In turn, FIG. 6C illustrates application of the subdivision rules to the control points 30xe2x80x2 of FIG. 6B which produce yet another set of control points 30xe2x80x3. As shown in FIGS. 6A-6C, the portion of the surface comprised of shaded regular patches grows with each subdivision. Patches adjacent to the extraordinary vertices 32a-32c, while shrinking with each application of the subdivision rules, nevertheless remain irregular and, hence, cannot be evaluated with the basis functions developed for regular patches (FIG. 4). Further, each subdivision consumes significant computing resources as software tracks increasing numbers of control vertices.
In general, in one aspect, a computer-based method for determining a property of a location on a computer surface model where the location is described by a set of parameters and the surface model is described by a set of control vertices having a corresponding set of subdivision rules, and the control vertices admit a parameterization of regular sets of control vertices, includes receiving input specifying coordinates of control vertices that describe the surface model, projecting the specified coordinates of the control vertices into an eigenspace derived from a matrix representation of the subdivision rules to produce a set of projected control vertices, determining which of a hierarchically nested set of regular tiles of the surface model contains the location, and evaluating the location as a function of a valence of one of the control vertices, the determined nested tile, and the set of projected control vertices. The evaluated location is stored in a computer memory.
Embodiments of the computer-based method may include the following. One of the control vertices may be a control vertex having an extraordinary valence. The subdivision rules may include Catmull-Clark and/or Loop subdivision rules. The evaluating may determine coordinates of the location. The evaluating may determine a derivative of any order of the surface model at the location. The computer-based method may also include processing the evaluation to determine a display characteristic such as shading or texture mapping. The evaluating may be done according substantially to:       s    ⁡          (              u        ,        v            )        =            ∑              i        =        1            K        ⁢                            ϕ          i                ⁡                  (                      u            ,            v                    )                    ⁢                        p          i                .            
as described below. The evaluating may be done according substantially to:
s(v, w)=Ĉ0T"PHgr"(v, w).
as described below. The computer-based method may produce a graphics display based on the evaluation. The projecting may include reading data from a file that includes inverse eigenvector matrix data of the eigenspace. The computer-based method may include reading data from a file that includes eigenvalue and eigenvector data of the eigenspace. Input may be received via a graphical user interface or via program variables.
In general, in one aspect, a computer-based method of evaluating a location of a computer surface model where the location is specified by a set of parameters and the surface is described by a set of control vertices having a corresponding set of subdivision rules, and the control vertices admit a parameterization of regulars sets of control vertices, and where one of the control vertices being a vertex having an extraordinary valance, includes receiving input specifying coordinates of the control vertices, evaluating the location as a function of the control vertices without explicitly subdividing the control vertices in accordance with the subdivision rules, and storing the evaluated location in a computer memory.
In general, in one aspect, a computer program product, disposed on a computer readable medium, for determining a property of a location on a computer surface model, where the location is specified by a set of parameters and the surface is described by a set of control vertices having a corresponding set of subdivision rules, and the control vertices admit a parameterization of regular sets of control vertices, includes instructions for causing a computer to receive input specifying coordinates of the control vertices, project the specified coordinates of the control vertices into an eigenspace derived from a matrix representation of the subdivision rules to produce a set of projected control vertices, determine which of a hierarchically nested set of regular tiles contains the location, and evaluate the location as a function of a valence of one of the control vertices, the determined nested tile, and the set of the projected control vertices. The evaluated location is stored in a computer memory.
Advantages may include one or more of the following.
Evaluation of a surface which admits a parameterization on a regular part of the control mesh requires no explicit subdividing, thus reducing programming complexity and consumption of processing resources. The evaluation computations are easily implemented and efficient. The techniques described can be used to quickly produce high quality curvature plots of subdivision surfaces. The computational cost of evaluation is comparable to that of a bi-cubic spline. The rapid and precise evaluation of a surface is crucial for many standard operations on surfaces such as picking, rendering and texture mapping. The evaluation technique further allows a large body of useful techniques from parametric surfaces to be transferred to subdivision surfaces, making them even more attractive as a free-form surface modeling tool.
Other features and advantages will be apparent from the following detailed description including the drawings and from the claims.